# coding:utf-8
# author:WHY
# time:2016-05-24

import copy

class Parser:
	# 语法分析器
	def __init__(self, tokens, grammar, begin):
		self.tokens = tokens		# 储存所有的Token
		self.grammar = grammar		# 储存语法结构
		self.begin = begin			# 语法的开始状态
		self.vn = set()				# 非终结符集合
		self.v = set() 				# 所有符号集合
		self.hashSet = {}			# 主要用来状态转移
		self.goto = {}				# GOTO表
		self.action = {}			# ACTION表
		
		# 统计终结符和非终结符
		for key, data in grammar.items():
			self.vn.add(key)
			for item in data:
				for i in item:
					self.v.add(i)
	
	def first(self, items, visit):
		# 求First集
		res = []
		if items[0] in visit:
			return (res, False)
		empty = True
		for item in items:
			if empty == False:
				return (res, False)
			if item not in self.vn:
				res.append(item)
				return (res, False)
			empty = False
			for der in self.grammar[item]:
				if len(der) == 0:
					empty = True
					continue
				visit.add(item)
				(ans, flag) = self.first(der, visit)
				res += ans
				temp = set(res)
				res = list(temp)
				visit.remove(item)
				if flag == True:
					empty = True
		return (res, empty)
		
	def makeTable(self):
		# 生成项目集 ACTION表 GOTO表
		self.grammar.setdefault('begin-1', [(self.begin,)])
		
		# 给推导式编号
		for vn, exp in self.grammar.items():
			for item in exp :
				temp = [vn]
				temp += list(item)
				self.hashSet.setdefault(hash(tuple(temp)), tuple(temp))
		
		initItem = {
			'data':('begin-1', self.begin),
			'pointPosition':1,
			'flag':['$end']
		}
		
		# 获取ACC标志
		self.accflag = hash(initItem['data'])
		
		initItemSet = {
			'id':self.getItemSetHash(self.closer(initItem, set())),
			'data':self.closer(initItem, set())
		}
		
		# 获取语法分析的初始状态
		self.parserBegin = initItemSet['id']
		
		self.c = []
		self.c.append(initItemSet)
		
		visit = set() 	# 判断项目集是否重复
		visit.add(initItemSet['id'])
 		for items in self.c:
			for v in self.v:
				res = self.getItemSet(items['data'], v)
				if len(res) == 0:
					continue
					
				newItemSet = {
					'id':self.getItemSetHash(res),
					'data':res
				}
				
				# 构造GOTO表
				if v in self.vn:
					self.goto.setdefault(items['id'], {})
					self.goto[items['id']].setdefault(v, newItemSet['id'])
					
				# 构造部分ACTION表  状态转移
				if v not in self.vn:
					self.action.setdefault(items['id'], {})
					self.action[items['id']].setdefault(v, {})
					self.action[items['id']][v] = {
						'flag':'s',
						'data':newItemSet['id']
					}
					
					
				if  newItemSet['id'] not in visit:
					visit.add(newItemSet['id'])
					self.c.append(newItemSet)
		
		# 构造ACTION表  归约
		for itemSet in self.c:
			for item in itemSet['data']:
				if len(item['data'])<=2:
					pass
				if item['pointPosition'] >= len(item['data']):
					id = hash(item['data'])
					self.action.setdefault(itemSet['id'], {})
					for v in item['flag']:
						self.action[itemSet['id']].setdefault(v, {})
						self.action[itemSet['id']][v] = {
							'flag':'r',
							'data':id
						}
		
	def parser(self):
		# 进行语法分析
		self.makeTable()
		# 初始化
		signal = []
		stateStack = []
		stateStack.append(self.parserBegin)
		
		self.tokens.append([0, 0, '$end', 'EOF'])
		
		while stateStack[-1] != self.accflag:
			token = self.tokens[0][2]
			if token == '$end' and signal[-1] == self.begin:
				break
			if token in self.action[stateStack[-1]].keys():
				thisAction = self.action[stateStack[-1]][token]
				
				# 对可归约状态进行归约
				if thisAction['flag'] == 'r' and thisAction['data'] != self.accflag:
					length = len(self.hashSet[thisAction['data']]) - 1 		# 获取回退步数
					if length != 0:
						stateStack = stateStack[0:-length]
					token = self.hashSet[thisAction['data']][0]
					if token in self.goto[stateStack[-1]].keys():
						thisGoto = self.goto[stateStack[-1]][token]
					stateStack.append(thisGoto)
					if length != 0:
						signal = signal[0:-length]
					signal.append(token)
				else:
					signal.append(token)
					self.tokens.pop(0)
					stateStack.append(thisAction['data'])
				
			else:		# 没有可转移的状态，不符合语法规范
				print "Error:%s:%s %s" %(self.tokens[0][0], self.tokens[0][1], self.tokens[0][3])
				break
		if signal[-1] == self.begin:
			return True
		else:
			return False
		
	def getItemSet(self, items, v):
		newItems = []
		for item in items:
			newItems += self.go(item, v)
		return newItems
		
	def closer(self, derivation, visit):
		# 获得从一个项目获得一串新的项目
		res = []
		# 空项目集  已经加入项目集    不需要求闭包
		if len(derivation) == 0 or \
			len(derivation['data']) == 0 or \
			hash(derivation['data']) in visit :
			return res

		id = self.getItemHash(derivation)		# 将自己加入闭包中
		if id not in visit:
			visit.add(id)
			res.append(derivation)
				
		if len(derivation['data']) <= derivation['pointPosition']: 
			return res  # 小圆点在最后的 返回自身
		
		if derivation['data'][derivation['pointPosition']] in self.vn:
			for item in self.grammar[derivation['data'][derivation['pointPosition']]]:
				newItem = [derivation['data'][derivation['pointPosition']]] + list(item)
				firstSet = []
				for flag in derivation['flag']:
					firstSet += self.first(tuple(list(derivation['data'][derivation['pointPosition'] + 1:]) + [flag]), set())[0]
				firstSet = set(firstSet)
				firstSet = list(firstSet)
				item = {
					'data':tuple(newItem),
					'pointPosition':1,
					'flag':firstSet
				}
				id = self.getItemHash(item)
				newRes = []
				if id not in visit:
					visit.add(id)
					res.append(item)
					newRes = self.closer(item, visit)
				res += newRes
			return res
		else:
			return res
			
	def go(self, item, v):
		# 圆点后移一位
		item = copy.copy(item)
		res = []
		if item['pointPosition'] < len(item['data']):		# 小圆点要在一个字符前面
			if item['data'][item['pointPosition']] != v:	
				return res									# 不符合转移条件
			item['pointPosition'] += 1
			newItems = self.closer(item, set())
			res += newItems
		return res
		
	def getItemHash(self, item):
		# 获取某个项目集的哈希值
		data = list(item['data'])
		data.sort()
		flag = list(item['flag'])
		flag.sort()
		temp = data + flag
		temp.append(item['pointPosition'])
		return hash(tuple(temp))
		
	def getItemSetHash(self, items):
		# 标记项目集
		s = set()
		for item in items:
			s.add(self.getItemHash(item))
		return hash(tuple(s))